﻿// 1998. 数组的最大公因数排序.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;
/*
https://leetcode.cn/problems/gcd-sort-of-an-array/description/

给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ：

如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。
如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true ；否则，返回 false 。



示例 1：

输入：nums = [7,21,3]
输出：true
解释：可以执行下述操作完成对 [7,21,3] 的排序：
- 交换 7 和 21 因为 gcd(7,21) = 7 。nums = [21,7,3]
- 交换 21 和 3 因为 gcd(21,3) = 3 。nums = [3,7,21]
示例 2：

输入：nums = [5,2,6,2]
输出：false
解释：无法完成排序，因为 5 不能与其他元素交换。
示例 3：

输入：nums = [10,5,9,3,15]
输出：true
解释：
可以执行下述操作完成对 [10,5,9,3,15] 的排序：
- 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [15,5,9,3,10]
- 交换 15 和 3 因为 gcd(15,3) = 3 。nums = [3,5,9,15,10]
- 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [3,5,9,10,15]


提示：

1 <= nums.length <= 3 * 104
2 <= nums[i] <= 105
*/


class Solution {
public:
    int f[100010];
    void init() {
        for (int i = 0; i < 100010; i++) f[i] = i;
    }

    int find(int x) {
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }
    void merge(int a, int b) {
        a = find(a); b = find(b);
        f[a] = b;
    }

    bool gcdSort(vector<int>& nums) {
        init();
        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i];
            for (int j = 2; j <= val / j; j++) {
                int flag = 0;
                while (val % j == 0) {
                    val /= j;
                    flag = 1;
                }
                if (1 == flag) {
                    merge(nums[i],j);
                }
            }

            if (val != 1) {
                merge(nums[i],val);
            }
        }

        vector<int> cp = nums;
        sort(cp.begin(),cp.end());

        for (int i = 0; i < cp.size(); i++) {
            if (cp[i] == nums[i]) continue;
            if (cp[i] != nums[i] && find(nums[i]) != find(cp[i])) {
                return false;
            }
        }


        return true;
    }
};

int main()
{
    Solution s;
    vector<int>  v{ 5,2,6,2 };
    cout << s.gcdSort(v) << endl;
}
 